#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 乘积最大子数组：https://leetcode.cn/problems/maximum-product-subarray/
using namespace std;
class Solution {
public:
    //1.状态表示：dp[i]: 以i位置结尾的所有子数组是的最大积
    //2.状态转移方程：dp[i]=max(nums[i],max(f*nums,g*nums))
    //3.初始化：f[0]=g[0]=nums[0]
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n);
        auto g=f;
        int ret=nums[0];
        f[0]=g[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            f[i]=max(nums[i],max(nums[i]*f[i-1],nums[i]*g[i-1]));
            g[i]=min(nums[i],min(nums[i]*f[i-1],nums[i]*g[i-1]));
            ret=max(ret,f[i]);
        }
        return ret;
    }
};